//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 
//
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 2
//输出：2
//解释：有两种方法可以爬到楼顶。
//1. 1 阶 + 1 阶
//2. 2 阶 
//
// 示例 2： 
//
// 
//输入：n = 3
//输出：3
//解释：有三种方法可以爬到楼顶。
//1. 1 阶 + 1 阶 + 1 阶
//2. 1 阶 + 2 阶
//3. 2 阶 + 1 阶
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 45 
// 
// Related Topics 记忆化搜索 数学 动态规划 👍 2385 👎 0

package leetcode.editor.cn;

class ClimbingStairs {
    public static void main(String[] args) {
        Solution solution = new ClimbingStairs().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*public int climbStairs(int n) {
            if (n <= 2) {
                return n;
            }

            // dp[i]表示爬到i楼层需要的的方法为dp[i]
            int[] dp = new int[3];
            dp[1] = 1;  // 由于没有楼层0，所有0不做初始化
            dp[2] = 2;
            int sum = 0;
            for (int i = 3; i <= n; i++) {  // 注意从3开始，且要到达n层
                sum = dp[1] + dp[2];
                dp[1] = dp[2];
                dp[2] = sum;
            }

            return dp[2];
        }*/

        // 按照0-1背包的思路
        public int climbStairs(int n) {
            // dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。
            int[] dp = new int[n + 1];
            // 表示重量
            int[] weight = {1, 2};
            // 初始化，方便后边推导出公式
            dp[0] = 1;
            // 先遍历背包,就是总阶梯
            for (int j = 1; j <= n; j++) {
                // 再遍历物品，就是第i个阶梯
                for (int i = 0; i < weight.length; i++) {
                    if (j >= weight[i]) {
                        dp[j] += dp[j - weight[i]];
                    }
                }
            }

            return dp[n];
        }

        /*public int climbStairs(int n) {
            if (n <= 1) return n;
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 2;
            for (int i = 3; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }

            return dp[n];
        }*/

    }
//leetcode submit region end(Prohibit modification and deletion)

}
